
//1011.在D天内送达包裹的能力
class Solution {
    //计算运载能力为x时需要的时间
    long long time(vector<int>& nums,long long x)
    {
        long long tmp=0,ret=0;
        for(auto e:nums)
        {
            if(e>x) return -1;
            tmp+=e;
            if(tmp>=x)
            {
                ret++;
                tmp=tmp==x?0:e;
            }
        }
        if(tmp) ret++;
        return ret;
    }

public:
    int shipWithinDays(vector<int>& weights, int days) {
        //船运载能力越强所需的时间就越短，是单调递减的可以使用二分来解决
        int n=weights.size();
        //右边界设置为如果货物全是weight的最大值当时间为days时需要的运载能力
        //(n-1)/days+1表示包裹数量除以天数向上取整，即一天至多需要运输多少个包裹
        long long left=0,right=ranges::max(weights)*((n-1)/days+1);
        while(left+1<right)
        {
            long long mid=left+(right-left)/2;
            int need=time(weights,mid);
            if(need>0&&need<=days) right=mid;
            else left=mid;
        }
        return right;
    }
};